from link_list.node.SinglyListNode import SinglyListNode


def reverseList(head: SinglyListNode) -> SinglyListNode:
    curr = head
    pre = None
    if head is None or head.next is None:
        return head

    while curr is not None:
        post = curr.next
        curr.next = pre
        pre = curr
        curr = post
    return pre


def reverseListRecursion(head: SinglyListNode) -> SinglyListNode:
    if head is None or head.next is None:
        return head
    resultList = reverseListRecursion(head.next)
    head.next.next = head
    head.next = None
    return resultList


first = SinglyListNode(3)
first.next = SinglyListNode(2)
first.next.next = SinglyListNode(1)
result = reverseList(first)
while result is not None:
    print(result.val, end="")
    result = result.next

print("")

first2 = SinglyListNode(8)
first2.next = SinglyListNode(6)
first2.next.next = SinglyListNode(3)
first2.next.next.next = SinglyListNode(2)
result2 = reverseListRecursion(first2)
while result2 is not None:
    print(result2.val, end="")
    result2 = result2.next
